Managing available memory is critically important to the performance and reliability of a computer system. Such systems must store vast quantities of data within limited memory address space. Data is commonly stored in the form of objects. Memory space allocated for an object is known as an object heap. Typically each computer program has its own object heap.
Objects comprise both data structures and operations, known collectively as methods. Methods access and manipulate data structures. Objects having identical data structures and common behavior can be grouped together into classes. Each object inherits the data structure and methods of the particular class from which it was instantiated. Further, a hierarchical inheritance relationship exists between multiple classes. For example, one class may be considered a parent of another, child class. The child class is said to be derived from the parent class and thus, inherits all of the attributes and methods of the parent class.
Object structure includes data and object reference fields. Object references may contain the memory addresses or other information associated with other memory locations and objects. The object 10 of FIG. 1 has an identifier field 12; data field/item 14 and object references 16, 18. In some applications, object references are referred to as pointers. The identifier field 12 contains processing instructions used only when the object 10 is compiled, so it is not necessarily stored with the object 10. Dashes distinguish the identifier field 12 from information stored at run time.
In FIG. 1, object references 16 are represented as arrows pointing to other objects 20. That is, the object reference 16 may comprise a pointer, which in turn, may include an actual memory address where an object is located within the object heap. A null value of object reference 18 is represented by an “X” within the corresponding field. Items 14 are contained by the object 10 and are referred to as internal objects, while objects 20 referenced by the object's 10 object references 16 are known as external objects.
The exemplary object 10 also has names 22 associated with it. Each name may comprise a labeled pointer to the object. Since names are only used by the compiler at compile time, they do not require any storage at run time. This fact is represented by the use of dashed boxes to enclose the name pointers. Note that external objects can also contain pointers to other objects recursively, creating an object with arbitrary depth.
The depth of an object is determined by counting the number of object references that must be followed to reach it, starting from a name. In FIG. 1, names 22 are at depth 0, and the object 10 is at depth 1. The external objects 20 are at depth 2. For consistency, the depth attributed to the manipulation of an object reference corresponds to the depth at which the object reference is stored. Thus, manipulations of object references 16 as shown in FIG. 1 are considered to be at depth 1.
Whenever a program creates a new object, available memory is reserved using a process known as memory allocation. The Java programming environment is one example of a programming framework that utilizes memory allocation. Given the limited amount of memory available in such an environment, it is important to deallocate memory reserved for data no longer in use. Otherwise, system performance will suffer as available memory is consumed.
A computer program known as a garbage collector empties unused memory that has been allocated by other programs. Generally, a garbage collection algorithm carries out storage management by automatically reclaiming storage. Garbage collectors are typically activated when an object heap becomes full. Garbage collection algorithms commonly determine if an object is no longer reachable by an executing program. A properly collectable object is unreachable either directly or through a chain of pointers.
Thus, the garbage collector must identify pointers directly accessible to the executing program. Further, the collector must identify references contained within that object, allowing the garbage collector to transitively trace chains of pointers. When the data structure of an object is deemed unreachable, the garbage collector reclaims memory. The memory is deallocated even if it has not been explicitly designated by the program.
Specific methods for memory reclamation include reference counting, mark-scan and copying garbage collection. In reference counting collection, each external object is associated with a count reflecting the number of objects that point to it. Every time a new pointer implicates an external object, the count is incremented. Conversely, the count is decremented every time an existing reference is destroyed. When the count goes to zero, the object and its associated count are deallocated.
A variation of the reference counting scheme, known as weighted reference counting, removes the requirement of referencing shared memory, but some bookkeeping is still required at run time. Another variation, known as lazy reference counting, reduces the run-time CPU requirements by deferring deallocation operations and then combining them with allocations, but does not eliminate them entirely.
An alternative method, mark-scan garbage collection, never explicitly deallocates external objects. Periodically, the garbage collection process marks all data blocks that can be accessed by any object. Unreachable memory is reclaimed by scanning the entire memory and deallocating unmarked elements.
Each cycle of the mark-scan algorithm sequentially operates in mark and sweep stages. In the mark stage, the collector scans through an object heap beginning at its roots, and attempts to mark objects that are still reachable from a root. Objects deemed reachable if it is referenced directly by a root or by a chain of objects reachable from a root. In the sweep stage, the collector scans through the objects and deallocates any memory reserved for objects that are unmarked as of completion of the mark stage. Some variations of mark-scan require that active program threads be halted during collection, while others operate concurrently.
Copying garbage collectors are similar to those of the mark-scan variety. However, instead of marking those items that can be reached by reference, all reachable data structures are periodically copied from one memory space into another. The first memory space can then be reclaimed in its entirety. A specific implementation of a copying garbage collector is a generational garbage collector, which partitions an object heap into new and old partitions. A generational garbage collector relies on a tendency for newer objects to cease to be used more frequently than older objects. Put another way, as an object is used over time, it becomes less and less likely that the object will cease being used.
One of the most efficient types of garbage collectors is a generational garbage collector. In a generational garbage collector, new objects are allocated in a young generation area of the heap. If an object continues to have references over a specified number of garbage collections cycles, the object is promoted to one or more old generation areas of the heap. A generational garbage collector performs garbage collection frequently on the young generation area of the heap, while performing garbage collection less frequently on old, or tenured, generation areas. This technique strives to match typical program behavior in that most newly created objects are short-lived, and are thus reclaimed during garbage collection of the young generation. Long-lived objects in the old generation areas tend to persist in memory. Hence, the old generation areas need to be garbage collected less frequently. This greatly reduces the effort involved in garbage collection because only the young generation area of the heap needs to be garbage collected frequently.
Despite the progresses afforded by the above garbage collection techniques, obstacles to memory management remain. One particular area of concern relates to processing delays attributable to garbage collectors. System performance must typically be interrupted, or paused, while a garbage collector executes. Associated delays of a second or more can severely degrade system performance. Such scenarios become exacerbated where extremely large caches are involved. For instance, a Java Virtual Machine, or JVM, routinely include larger caches (larger than four gigabytes) that must be frequently updated and modified. Conventional JVM garbage collection models incur massive and unacceptable response time drop-offs as objects are updated in the cache sitting in the old space. It may take an unacceptable amount of time to promote the object from the new space to the old space. Long delays may additionally be suffered as the corresponding old object is garbage collected from the tenured heap, which may be larger than four gigabytes.
For at least the above reasons, there exists a need for an improved manner of managing stored objects, and more particularly, for deallocating objects from memory.